package first.forHuaWei.贪心;

/**
 * @ClassName LC134
 * @description:
 * @author: 荣燊
 * @create: 2021-09-06 10:49
 **/
public class LC134 {
    // 加油站，循环数组，
    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
    }

    // 暴力遍历
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i=0; i<n; i++) {
            // 直接跳过第一步都不满足的起点
            if (gas[i] < cost[i]) {
                continue;
            }
            // 剩余油量
            int cur = gas[i] - cost[i];
            // 所在位置，到达下一步
            int idx = (i+1) % n;
            //
            while (idx != i) {
                cur += gas[idx] - cost[idx];
                if (cur < 0) {
                    break;
                }
                // 到达下一步
                idx = (idx+1) % n;
            }
            if (idx == i) {
                return i;
            }

        }
        return -1;
    }


    // 在位置i和位置k之间的所有位置，都不可能是一个合法起点。也就是说，随着起点i验证失败，我们可以否决掉方案不仅仅是位置i，
    // 而是[i, k]这些位置。
    //链接：https://leetcode-cn.com/problems/gas-station/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-zsgqp/
    public static int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        int i= 0;
        while (i < n) {
            int sumGas = 0;
            int sumCost = 0;
            int cnt = 0; // i与j的差值
            while (cnt < n) {
                int j = (i+cnt) % n;
                sumGas += gas[j];
                sumCost += cost[j];
                if (sumCost > sumGas) {
                    break;
                }
                cnt++;
            }
            // 找到正确节点
            if (cnt == n) {
                return i;
            } else {
                i = i+cnt+1;
            }
        }
        return -1;
    }
}
